package LearnAlgorithm.f_字符串;

/*
搞清楚了一个事：
	
	1.蓝桥杯KMP一个样
	2.考研KMP一个样
	
	3.网课KMP一个样
	
	1&2都是一个思想；3自己一个思想
 */
public class m字符串匹配KMP {
	public static void main(String[] args) {
		String string = "ABAxBxABAxBxABAxBxABA";
		String keys = "xABA";
		long before = System.currentTimeMillis();
		System.out.println(lanQiaoKMP(string, keys));
		util.Util.duration(before);
		long before2 = System.currentTimeMillis();
		System.out.println(findForce(string, keys));
		util.Util.duration(before2);
		long before3 = System.currentTimeMillis();
		System.out.println(OtherKMP(string, keys));
		util.Util.duration(before3);
		String testMother = "aaaaaaaaaaa";
		String testChild = "aaaa";
		System.out.println(lanQiaoKMPPlusCount(testMother, testChild));
	}
	
	/**
	 * O(M+N)
	 * 蓝桥杯&考研的KMP
	 * 不会有没考虑到的情况，是完全正确的
	 * @param mother
	 * @param child
	 * @return count
	 */
	public static int lanQiaoKMPPlusCount(String mother, String child) {//child就是目标字串
		if (mother == null || child == null || mother.length() == 0 || child.length() == 0) {
			return -1;//健壮性判断；两串是空串
		}
		if (child.length() > mother.length()) {
			return -1;//健壮性判断；child长于mother
		}
		int[] next = nextKMP(child);//生成child的next[]
		int motherCurrent = 0;//定义mother指针
		int childCurrent = 0;//定义child指针
		int motherLength = mother.length();
		int childLength = child.length();
		int count = 0;//定义匹配成功的次数
		while (motherCurrent < motherLength) {//比较循环
			if (childCurrent == -1 || mother.charAt(motherCurrent) == child.charAt(childCurrent)) {//child的第一个元素就与motherCurrent指向的元素不等(这里就体现了next[0] = -1的理由)；两串的指针指向的元素相等
				//两串指针都向后移动
				motherCurrent++;
				childCurrent++;
			} else {//在匹配了一些字符后，childCurrent指向的元素 != motherCurrent指向的元素
				childCurrent = next[childCurrent];//childCurrent根据next数组进行回溯；motherCurrent不变
			}
			if (childCurrent == childLength) {//判断child是否读完
				count++;//读完；次数更新
				motherCurrent--;//因为最后一个child元素读取并且匹配成功后，两串指针都有一次向后移动，造成了childCurrent == childLength；下面的步骤我们假设child最后一位元素失配，那么理所应当motherCurrent应该-1来符合“motherCurrent指向目标子串最后一个元素”的情况
				childCurrent = next[childCurrent - 1];//当前因为读完所以childCurrent一定指向最后一个child的元素的后面(因为childCurrent == childLength)；我们假设这最后一个元素失配；那么childCurrent回溯childCurrent = next[childCurrent - 1]
//				return motherCurrent - childCurrent;//读完；匹配完全相等；返回mother中找到的目标字串的首索引
			}
		}
		return count;//mother中未找到目标字串；匹配失败；
	}
	
	/**
	 * O(M+N)
	 * 蓝桥杯&考研的KMP
	 * @param mother
	 * @param child
	 * @return
	 */
	public static int lanQiaoKMP(String mother, String child) {//child就是目标字串
		if (mother == null || child == null || mother.length() == 0 || child.length() == 0) {
			return -1;//健壮性判断；两串是空串
		}
		if (child.length() > mother.length()) {
			return -1;//健壮性判断；child长于mother
		}
		int[] next = nextKMP(child);//生成child的next[]
		int motherCurrent = 0;//定义mother指针
		int childCurrent = 0;//定义child指针
		int motherLength = mother.length();
		int childLength = child.length();
		while (motherCurrent < motherLength) {//比较循环
			if (childCurrent == -1 || mother.charAt(motherCurrent) == child.charAt(childCurrent)) {//child的第一个元素就与motherCurrent指向的元素不等(这里就体现了next[0] = -1的理由)；两串的指针指向的元素相等
				//两串指针都向后移动
				motherCurrent++;
				childCurrent++;
			} else {//在匹配了一些字符后，childCurrent指向的元素 != motherCurrent指向的元素
				childCurrent = next[childCurrent];//childCurrent根据next数组进行回溯；motherCurrent不变
			}
			if (childCurrent == childLength) {//判断child是否读完
				return motherCurrent - childCurrent;//读完；匹配完全相等；返回mother中找到的目标字串的首索引
			}
		}
		return -1;//mother中未找到目标字串；匹配失败；
	}
	
	/***
	 * O(N)
	 * NEXT数组生成
	 * 蓝桥杯&考研的生成思想
	 * 将来的我如果复习时看不懂这里的代码，就去画画图
	 * 或者直接理解成固定写法就行了，死记硬背
	 * @param string
	 * @return
	 */
	public static int[] nextKMP(String string) {
		int length = string.length();//定义child串长度
		int[] next = new int[length];//定义next数组
		char[] stringArr = string.toCharArray();//定义child的char[]
		next[0] = -1;//固定写法；默认首元素值 = -1
		if (length == 1) {//如果child只有1个元素
			return next;//next生成完毕
		}
		next[1] = 0;//固定写法；child第二个元素的next数组的值 = 0；因为根据蓝桥杯思想第二个元素前的子串不满足“含有前后缀”，因为只有一个元素！
		int j = 1;//固定写法；定义遍历child的指针；从1开始；因为next[0]固定为-1所以从0开始没意义
		int k = next[j];//固定写法；定义当前指针指向的child元素的在next[]中对应的值
		while (j < length - 1) {//循环遍历next,作用是将1~next.length-1所有索引的值填充
			//如果child[j]==child[next[j]],
			//当child[j+1]在实战中失配时,
			//指针应移动到child[next[j] + 1],
			//换言之就是child[j+1]这个元素的在next[]中的对应的索引的值是"next[j] + 1"
			//此外，当k(也就是next[j]) = -1时，即k被赋值-1；当child[j+1]在实战中失配时，指针也应移动到child[next[j] + 1]
			if (k < 0 || stringArr[j] == stringArr[k]) {
				next[++j] = ++k;//++k 意味着: 先自增(k + 1),再赋值；此行也可以写成next[j + 1] = k + 1; j++; k++;
			} else {
				//如果child[j] != child[next[j]]
				//那么k(也就是next[j])被赋值成next[k]；这是一种类似递归的“回溯”；这种“回溯”充分利用了“前后缀”的概念，十分巧妙
				k = next[k];//固定写法；当k = 0时，这里k会被赋值成-1
			}
		}
		return next;
	}
	
	public static int OtherKMP(String mother, String child) {
		int[] next = OtherNextKMP(child);
		int motherCurrent = 0;
		int childCurrent = 0;
		while (motherCurrent < mother.length()) {
			if (mother.charAt(motherCurrent) == child.charAt(childCurrent)) {
				motherCurrent++;
				childCurrent++;
			} else if (childCurrent > 0) {
				childCurrent = next[childCurrent - 1];//childCurrent指针前面的元素(childCurrent-1)在next[]中的对应的值赋给childCurrent
			} else {
				motherCurrent++;
			}
			if (childCurrent == child.length()) {
				return motherCurrent - childCurrent;
			}
		}
		return -1;
	}
	
	public static int[] OtherNextKMP(String string) {
		int[] next = new int[string.length()];
		next[0] = 0;
		int k = 0;
		int i = 1;
		while (i < next.length) {
			if (string.charAt(i) == string.charAt(k)) {
				k++;
				next[i] = k;
				i++;
				//next[i++] = ++k;
			} else {
				if (k == 0) {
					next[i] = 0;
					i++;
				} else {
					k = next[k - 1];
				}
			}
		}
		return next;
	}
	
	/**
	 * O(M*N)
	 * 暴力
	 * @param mother
	 * @param child
	 * @return
	 */
	public static int findForce(String mother, String child) {
		int motherBegin = 0;
		int motherCompareIndex = motherBegin;
		int childCurrentIndex = 0;
		while (motherCompareIndex < mother.length()) {
			if (mother.charAt(motherCompareIndex) == child.charAt(childCurrentIndex)) {
				motherCompareIndex++;
				childCurrentIndex++;
				if (childCurrentIndex == child.length()) {
					return motherBegin;
				}
			} else {
				motherBegin++;
				motherCompareIndex = motherBegin;
				childCurrentIndex = 0;
			}
		}
		return -1;
	}
}
